#ifndef __DETECTCYCLE_H__
#define __DETECTCYCLE_H__
#include "ListHeader.h"

/*
* leetcode 142 环形链表
* 给定一个链表的头节点  head ，返回链表开始入环的第一个节点
* 如果链表无环，则返回 null
*/

/*
* 判断是否有环
* 使用快慢指针, 当快指针和慢指针相遇时, 必定是在环中相遇
*/

/*
* 找出环的入口
* n1 -> n2 -> n3 -> n4 -> n5
*                    ↑     ↓
*                   n9    n6
*                    ↑     ↓
*                   n8 <- n7
* 假设: x 为 入口的长度 (n1-n4)
*       y 为 相交处, 设 n7 (n4-n7)
*       z 为 环剩余长度 (n7-n4)
* slow = x + y
* fast = x + y + n(y + z)
* 2slow = fast
* x = (n - 1)(y + z) + z
* 所以, 无论 fast 转几圈, x == z
*/

List* DetectCycle(List* head) {
	List* slow = head;
	List* fast = head;

	while (fast != nullptr && fast->next != nullptr) {
		slow = slow->next;
		fast = fast->next->next;

		//快慢指针在环中相遇
		if (slow == fast) {
			List* indexXY = fast;
			List* indexX = head;

			//计算Z
			while (indexX != indexXY) {
				indexX = indexX->next;
				indexXY = indexXY->next;
			}

			return indexX;
		}
	}

	return nullptr;
}

#endif // !__DETECTCYCLE_H__

